package com.zyk.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author zhangsan
 * @date 2021/4/4 19:39
 */
public class J31 {

    /** https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/ */
    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        // 辅助栈来实现, 因为不包含重复元素,所以遇到popped与栈顶相等的数就应立马出栈
        Deque<Integer> stack = new ArrayDeque<>();
        int popI = 0;
        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek().equals(popped[popI])) {
                stack.pop();
                popI++;
            }
        }
        return stack.isEmpty();
    }


    // for test
    public static void main(String[] args) {

    }

}
